Stacks

Introduction

A stack is a linear data structure and very much useful in various applications of computer science. The implementation of the majority of systems programs is simplified using this data structure. Before discussing this data structure, let us first consider a few examples of the stack phenomenon.

Shunting of trains in a railway yard

Suppose there is a railway yard with a single track. Trains enter into the railway yard for placement, and when they exit, it is just in opposite order to that they had entered, i.e. the last train comes out first (see Figure 4.1).

Shipment in a cargo

For the shipment of goods, they are loaded into a cargo compartment. At the destination, they are unloaded exactly in the opposite sequence to that in which they were loaded. That is, the goods loaded last get unloaded first.

Plates on a tray

Suppose a chef placed the dishes on a tray one above the other. The waiter served the dishes to the customers in the opposite order that the chef placed them, that is, the dish at the top which

Figure 6.1 Some examples of stacks.

was placed last by the chef is serviced first. The first dish placed by the chef on the tray is serviced last by the waiter.

From the above examples, it is clear that a stack is something which follows the last-in first-out strategy. This is why a stack is alternatively termed LIFO (Last-In-First-Out).

Definition

A stack is an ordered collection of homogeneous data elements where the insertion and deletion operations take place at one end only.

Like an array and a linked list, a stack is also a linear data structure but the only difference is that in the case of the former two, insertion and a deletion operations can take place at any position. The insertion and deletion operations in the case of a stack are specially termed PUSH and POP, respectively, and the position of the stack where these operations are performed is known as the TOP of the stack. An element in a stack is termed an ITEM. The maximum number of elements that a stack can accommodate is termed SIZE. Figure 6.2 shows a typical view of a stack data structure.

Figure 6.2 Schematic diagram of a stack.

Representation of a Stack

A stack may be represented in the memory in various ways. There are two main ways: using a one-dimensional array and a single linked list. Representations of stacks in a memory are discussed in the following two sections.

Array Representation of Stacks

First we have to allocate a memory block of sufficient size to accommodate the full capacity of the stack. Then, starting from the first location of the memory block, the items of the stack can be stored in a sequential fashion.

In Figure 6.3(a), Itemi denotes the ith item in the stack; l and u denote the index range of the array in use; usually the values of these indices are 1 and SIZE respectively. TOP is a pointer to point the position of the array up to which it is filled with the items of the stack. With this representation, the following two ways can be stated:

EMPTY: TOP < l

FULL: TOP ³ u

Figure 6.3 Two ways of representing stacks.

Linked List Representation of Stacks

Although array representation of stacks is very easy and convenient but it allows the representation of only fixed sized stacks. In several applications, the size of the stack may vary during program execution. An obvious solution to this problem is to represent a stack using a linked list. A single linked list structure is sufficient to represent any stack. Here, the DATA field is for the ITEM, and the LINK field is, as usual, to point to the next item. Figure 4.3(b) depicts such a stack using a single linked list.

In the linked list representation, the first node on the list is the current item that is the item at the top of the stack and the last node is the node containing the bottom-most item. Thus, a PUSH operation will add a new node in the front and a POP operation will remove a node from the front of the list. The SIZE of the stack is not important here because this representation allows dynamic stacks instead of static stacks, as with arrays.

In the linked list representation of a stack, whether a stack is empty or not can be ascertained by testing the LINK field of the STACK_HEAD node. Note that a test for overflow is not applicable in this case.

Operations on Stacks

The basic operations required to manipulate a stack are:

PUSH To insert an item into a stack

POP To remove an item from a stack

STATUS To know the present state of a stack

Let us define all these operations of a stack. First, we will consider the above-mentioned operations for a stack represented by an array.

Algorithm Push_Array

Input: The new item ITEM to be pushed onto it.

Output: A stack with a newly pushed ITEM at the TOP position.

Data structure: An array A with TOP as the pointer.

Steps:

1. If TOP ³ SIZE then

2. Print “Stack is full”

3. Else

4. TOP = TOP + 1

5. A[TOP] = ITEM

6. EndIf

7. Stop

Here, we have assumed that the array index varies from 1 to SIZE and TOP points the location of the current top-most item in the stack. The following algorithm Pop_Array defines the POP of an item from a stack which is represented using an array A.

Algorithm Pop_Array

Input: A stack with elements.

Output: Removes an ITEM from the top of the stack if it is not empty.

Data structure: An array A with TOP as the pointer.

Steps:

1. If TOP < 1 then

2. Print “Stack is empty”

3. Else

4. ITEM = A[TOP]

5. TOP = TOP – 1

6. EndIf

7. Stop

In the following algorithm Status_Array, we test the various states of a stack such as whether it is full or empty, how many items are right now in it, and read the current element at the top without removing it, etc.

Algorithm Status_Array

Input: A stack with elements.

Output: States whether it is empty or full, available free space and item at TOP.

Data structure: An array A with TOP as the pointer.

Steps:

1. If TOP < 1 then

2. Print “Stack is empty”

3. Else

4. If (TOP ³ SIZE) then

5. Print “Stack is full”

6. Else

7. Print “The element at TOP is”, A[TOP]

8. free = (SIZE – TOP)/SIZE * 100

9. Print “Percentage of free stack is”, free

10. EndIf

11. EndIf

12. Stop

Now let us see how the same operations can be defined for a stack represented with a single linked list.

Algorithm Push_LL

Input: ITEM is the item to be inserted.

Output: A single linked list with a newly inserted node with data content ITEM.

Data structure: A single linked list structure whose pointer to the header is known from

STACK_HEAD and TOP is the pointer to the first node.

Steps:

1. new = GetNode(NODE)

/* Insert at front */

2. new®DATA = ITEM

3. new®LINK = TOP

4. TOP = new

5. STACK_HEAD®LINK = TOP

6. Stop

Algorithm Pop_LL

Input: A stack with elements.

Output: The removed item is stored in ITEM.

Data structure: A single linked list structure whose pointer to the header is known from STACK_HEAD and TOP is the pointer to the first node.

Steps:

1. If TOP = NULL

2. Print “Stack is empty”

3. Exit

4. Else

5. ptr = TOP®LINK

6. ITEM = TOP®DATA

7. STACK_HEAD®LINK = ptr

8. TOP = ptr

9. EndIf

10. Stop

The operation Status now can be defined as follows:

Algorithm Status_LL( )

Input: A stack with elements.

Output: Status information such as its state (empty or full), number of items, item at the TOP.

Data structure: A single linked list structure whose pointer to the header is known from STACK_HEAD and TOP is the pointer to the first node.

Steps:

1. ptr = STACK_HEAD®LINK

2. If (ptr = NULL) then

3. Print “Stack is empty”

4. Else

5. nodeCount = 0

6. While (ptr ¹ NULL) do

7. nodeCount = nodeCount + 1

8. ptr = ptr®LINK

9. EndWhile

10. Print “The item at the front is”, TOP®DATA, “Stack contains”, nodeCount, “Number of items”

11. EndIf

12. Stop

Applications of Stacks

Various applications of stacks are known. A classical application in a compiler design is the evaluation of arithmetic expressions; here the compiler uses a stack to translate an input arithmetic expression into its corresponding object code. Some machines are also known which use built-in stack hardware called ‘stack machine’. Another important application of a stack is during the execution of recursive programs; some programming languages use stacks to run recursive programs. One important feature of any programming language is the binding of memory variables. Such binding is determined by the scope rules. There are two scope rules known: the static scope rule and the dynamic scope rule. Implementation of such scope rules is possible using a stack known as a run time stack.

The following subsections highlight the above-mentioned applications of stacks.

Evaluation of Arithmetic Expressions

An arithmetic expression consists of operands and operators. Operands are variables or constants and operators are of various types such as arithmetic unary and binary operators [for example, – (unary), + (addition), – (subtraction), * (multiplication), / (division), ^ (exponentiation), % (remainder modulo), etc.], relational operators (for example, <, >, <=, < >, >=, etc.), and Boolean operators (such as, AND, OR, NOT, XOR, etc.). In addition to these, parentheses such as ‘(’ and ‘)’ are also used. A simple arithmetic expression is cited below:

A + B * C / D – E ^ F * G

The problem to evaluate this expression is the order of evaluation. There are two ways to fix it. First, we can assign to each operator a precedence and associativity. For example, a set of usual operators with their precedence and associativity is given in Table 4.1.

Table 4.1 Precedence and associativity of operators

Operators Precedence Associativity

– (unary), +(unary), NOT 6 –

^ (exponentiation) 6 Right to left

* (multiplication), / (division) 5 Left to right

+ (addition), – (subtraction) 4 Left to right

<, <=, +, < >, >= 3 Left to right

AND 2 Left to right

OR, XOR 1 Left to right

Thus, with the above rules of precedence and associativity of operators, the evaluation will take place for the above-mentioned expression in the sequence (sequence is according to the number 1, 2, 3, …, etc.) stated below:

It should be noted that the above rules for precedence and associativity vary from one programming language to another.

Another way of fixing the order of evaluation is parenthesizing the expression fully; this allows one to override the rules for precedence and associativity. The following is the parenthesized version of the same expression:

Input: ((A + B) * ((C/D) – (E ^ (F * G))))

(A fully parenthesized expression)

With this parenthesization, the innermost parenthesis part (called sub expression) will be evaluated first, then the next innermost, and so on; such a sequence of evaluations is shown below:

Whatever way we may specify the order of evaluations, the problem is that we must scan the expression from left to right repeatedly. Hence, the above-mentioned processes are inefficient because of the repeated scanning required. Another problem is the ambiguity about how the compiler can resolve to generate a correct code for a given expression. The last problem mainly occurs for a partially parenthesized expression. These problems can be solved in the following two steps:

1. Conversion of a given expression into a special notation

2. Evaluation/production of an object code using a stack.

Notations for arithmetic expressions

There are three notations to represent an arithmetic expression, viz. infix, prefix and postfix (or suffix). The conventional way of writing an expression is called infix. For example,

A + B, C – D, E * F, G/H, etc.

Here, the notation is

<operand> <operator> <operand>.

This is called infix because the operator comes in between the operands. The prefix notation, on the other hand, uses the convention

Here, the operator come before the operands. The following are simple expressions in prefix notation:

+AB, –CD, *EF, /GH, etc.

The prefix notation was introduced by the Polish mathematician Jan Lukasiewicz and hence also termed Polish notation.

The last notation is called the postfix (or suffix) notation where the operator is suffixed by operands:

The following expressions are in postfix notation:

AB+, CD–, EF*, GH/, etc.

The postfix notation is just reverse of the Polish notation, hence it is also termed reversed Polish notation.

It may be noted that in all of the above notations, a unary operator precedes its operand.

An expression given in infix notation can easily be converted into its equivalent prefix or postfix notation. The following rule is applied to convert an infix expression into a postfix form.

● Assume the fully parenthesized version of the infix expression.

● Move all operators so that they replace their corresponding right part of parentheses.

● Remove all parentheses.

The following example illustrates this conversion. For simplicity, let us consider a fully parenthesized expression.

Input: ((A + ((B ^ C) – D)) * (E – (A/C)))

(A fully parenthesized expression)

(Arrows point from operators to their corresponding right parenthesis.)

((A ((B C ^ D – + (E (AC / – *

(Operators are moved to their respective right parentheses.)

Output: A B C ^ D – + E A C / – *

(All parentheses are removed yielding the postfix expression.)

A similar technique can be applied to obtain the prefix notation for a given infix notation but moving the operators corresponds to the left parenthesis.

Three notations for the given arithmetic expression are listed below:

Infix: ((A + ((B ^ C) – D)) * ( E – (A/C)))

Prefix: * + A – ^ BCD – E/AC

Postfix: ABC ^ D – + EAC / – *

The following points may be observed from the above three notations:

1. In both prefix and postfix equivalents of an infix expression, the variables are in the same relative positions.

2. The expressions in prefix or postfix form are completely parenthesis free.

3. The operators are rearranged according to the rules of precedence of operators.

Out of these three notations, the postfix notation has certain advantages over the other notations from the computational point of view. The main advantage of postfix is its evaluation. During the evaluation of an expression in postfix notation it is no longer required to scan the expression from left to right several times, but scanning is required exactly once. This is possible using a stack and will be discussed shortly.

Thus, evaluation of an expression is a two-step process. First, we have to convert the expression into its postfix notation, and then evaluate this expression in postfix notation. In each step, the stack is the main data structure that is used to accomplish these tasks.

The uses of the stack for the purpose and the above-mentioned procedures are discussed below. We will assume the array representation of a stack in our discussions.

Conversion of an infix expression to postfix expression

To formalize the conversion method, we will assume simple arithmetic expressions containing the +, –, *, /, and ^ (exponentiation) operators only (i.e. without unary operators, Boolean operators and relational operators). The expression may be parenthesized or unparenthesized.

First, we have to append the symbol ‘)’ as the delimiter at the end of a given infix expression and initialize the stack with ‘(’. These symbols ensure that either the input or the stack is exhausted.

Our next step is iterative: read one input symbol at a time and decide whether it has to be pushed onto the stack or not. This decision will be governed by Table 4.2.

Table 4.2 In-stack and in-coming priorities of symbols

Symbol In-stack In-coming

priority value priority value

+ – 2 1

* / 4 3

^ 5 6

operand 8 7

( 0 9

) – 0

From the table, it can be noted that for a symbol we have considered two priority values, viz. in-stack priority and in-coming priority values. A symbol will be pushed onto the stack if its in-coming priority value is greater than the in-stack priority value of the top-most element. Similarly, a symbol will be popped from the stack if its in-stack priority value is greater than or equal to the in-coming priority value of the in-coming element. In order to define the algorithm, we will assume the following functions:

ReadSymbol( ): From a given infix expression, this will read the next symbol.

ISP(X): Returns the in-stack priority value for a symbol X.

ICP(X): This function returns the in-coming priority value for a symbol X.

Output(X): Append the symbol X into the resultant expression.

Let as assume that a stack of capacity SIZE is known and TOP is the current pointer in it. PUSH and POP are usual operations of the stack.

Algorithm InfixToPostfix

Input: E, simple arithmetic expression in infix notation delimited at the end by the right parenthesis ‘)’, incoming and in-stack priority values for all possible symbols in an arithmetic expression.

Output: An arithmetic expression in postfix notation.

Data structure: Array representation of a stack with TOP as the pointer to the top-most element.

Steps:

1. TOP = 0, PUSH(‘(‘) // Initialize the stack

2. While (TOP > 0) do

3. item = E.ReadSymbol( ) // Scan the next symbol in infix expression

4. x = POP( ) // Get the next item from the stack

5. Case: item = operand // If the symbol is an operand

6. PUSH(x) // The stack will remain same

7. Output(item) // Add the symbol into the output expression

8. Case: item = ‘)’, // Scan reaches to its end

9. While x ¹ ‘(’ do // Till the left match is not found

10. Output(x)

11. x = POP( )

12. EndWhile

13. Case: ISP(x) ³ ICP(item)

14. While (ISP(x) ³ ICP(item)) do

15. Output(x)

16. x = POP( )

17. EndWhile

18. PUSH(x)

19. PUSH (item)

20. Case: ISP(x) < ICP(item)

21. PUSH(x)

22. PUSH (item)

23. Otherwise:

Print “Invalid expression”

24. EndWhile

25. Stop

Note: This is a procedure irrespective of the type of memory representation of the stack to convert an infix expression to its postfix form using the basic operations of the stack, namely PUSH and POP. These operations can be replaced with their respective versions and hence implementable to stack with any type of memory representation.

Example 6.1

Let us illustrate the procedure InfixToPostfix with the following arithmetic expression:

Input: (A + B) ^ C – (D * E) / F) (infix form)

Symbol reading: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Read Stack Output

symbol

Initial (

1 ((

2 (( A

3 ((+ A

4 ((+ AB

5 ( AB+

6 (^ AB+

7 (^ AB + C

8 ( – AB + C ^

9 ( – ( AB + C ^

10 ( – ( AB + C ^ D

11 ( – ( * AB + C ^ D

12 ( – ( * AB + C ^ DE

13 ( – AB + C ^ DE *

14 ( – / AB + C ^ DE *

15 ( – / AB + C ^ DE * F

16 AB + C ^ DE * F / –

Output: A B + C ^ DE * F / – (postfix form)

The above procedure assumes that the input infix expressions are according to the right syntax. So, if the input expression is not correct, its postfix form will not be correct. Extending the same idea, we can incorporate relational, Boolean and unary operators in the above procedure.

Evaluation of a postfix expression

For a given expression in postfix notation, it can be easily evaluated. The following algorithm EvaluatePostfix is used to evaluate an arithmetic expression in postfix notation using a stack.

Algorithm EvaluatePostfix

Input: E, an expression in postfix notation, with values of the operands appearing in the expression.

Output: Value of the expression.

Data structure: Array representation of a stack with TOP as the pointer to the top-most element.

Steps:

1. Append a special delimiter ‘#’ at the end of the expression

2. item = E.ReadSymbol( ) // Read the first symbol from E

3. While (item ¹ ‘#’) do

4. If (item = operand) then

5. PUSH(item) // Operand is the first push into the stack

6. Else

7. op = item // The item is an operator

8. y = POP( ) // The right-most operand of the current operator

9. x = POP( ) // The left-most operand of the current operator

10. t = x op y // Perform the operation with operator ‘op’ and operands x, y

11. PUSH(t) // Push the result into stack

12. EndIf

13. item = E.ReadSymbol( ) // Read the next item from E

14. EndWhile

15. value = POP( ) // Get the value of the expression

16. Return(value)

17. Stop

Example 6.2

To illustrate the algorithm EvaluatePostfix, let us consider the following expression:

Infix: A + (B * C) / D

Postfix: A B C * D / +

Input: A B C * D / + # with A = 2, B = 3, C = 4, and D = 6

Read symbol Stack

A 2 Push(A = 2)

B 2 3 Push(B = 3)

C 2 3 4 Push(C = 4)

* 2 12 Pop(4), Pop(3), Push(T = 12)

D 2 12 6 Push(D = 6)

/ 2 2 Pop(6), Pop(12), Push(T = 2)

+ 4 Pop(2), Pop(2), Push(T = 4)

# value = Pop( )

Implementation of Recursion

Recursion is an important tool to describe a procedure having several repetitions of the same. A procedure is termed recursive if the procedure is defined by itself. As a simple example, let us consider the case of calculation of the factorial value for an integer n.

n! = n × (n – 1) × (n – 2) × ··· × 3 × 2 × 1

n! = n × (n – 1)!

The last expression is the recursive description of the factorial whereas the first is the iterative definition. Using a pseudo code, the above two types of definitions are expressed as follows:

Factorial_I

Input: An integer number N.

Output: The factoral value of N, that is N!.

Remark: Code using the iterative definition of factorial.

Steps:

1. fact =1

2. For (i = 1 to N) do

3. fact = i * fact

4. EndFor

5. Return(fact) // Return the result

6. Stop

Here, Step 2 defines the iterative definition for the calculation of a factorial. Now, let us see the recursive definition of the same.

Factorial_R //Code using the recursive definition of factorial

Input: An integer number N.

Output: The factoral value of N, that is N!.

Remark: Code using the recursive definition of factorial.

Steps:

1. If (N = 0) then // Termination condition of repetition

2. fact = 1

3. Else

4. fact = N * Factorial_R(N – 1)

5. EndIf

6. Return(fact) // Return the result

7. Stop

Here, Step 4 recursively defines the factorial of an integer N. This is actually a direct translation of n! = n * (n – 1)! in the form of Factorial_R (n) = n * Factorial_R (n – 1). This definition implies that n! will be calculated if (n – 1)! is known, which in turn if (n – 2)! is known and so on until n = 0 when it returns 1 (Step 1).

The question that arises is how this definition can be implemented. We will see that a data structure stack can be used for this purpose. Some programming languages such as C, Pascal, which have a dynamic memory management mechanism, can directly accept the recursive definition of procedures; compilers of these programming languages are responsible to produce an object code suitable for execution using a stack (called run time stack). In other programming languages such as FORTRAN, COBOL, BASIC, which do not have a dynamic memory management mechanism, it is the user’s responsibility to define and maintain the stack in order to implement the recursive definition of the procedure.

For an illustration, let us consider the calculation of 5! using the recursive definition. To do this, the following steps are needed:

Steps:

1. 5! = 5*4!

2. 4! = 4*3!

3. 3! = 3*2!

4. 2! = 2*1!

5. 1! = 1*0!

6. 0! = 1

7. 1! = 1

8. 2! = 2

9. 3! = 6

10. 4! = 24

11. 5! = 120

Here, it is required to push the intermediate calculations till the terminal condition is reached. In the above calculation for 5!, Steps 1 to 6 are the push operations. Then subsequent pop operations will evaluate the value of intermediate calculations till the stack is exhausted.

To control the recursion, we have to maintain the following stacks:

Stack(s) for parameter(s) // To store the parameter(s) with which the recursion is defined

Stack(s) for local variable(s) // To hold the local variable(s) that are used within the definition

A stack to hold the return address.

From the above list of stacks it is evident that the number of stacks required is as many as there are parameters in the procedure. For some procedure which does not use any local variable, no stack is required for that purpose. Similarly, a stack to hold the return address may not be required for some recursive procedure.

Details about implementing recursive procedures using a stack are illustrated in the following sections with some well-known problems. Let us assume that all stacks are represented using an array structure. Also, assume that the sizes of stacks are adequate to run a procedure.

We will illustrate the implementation of three popular recursive computations:

1. Calculation of factorial value

2. Quick sort

3. Tower of Hanoi problem

For each problem, we will describe the recursive description, then the translation of the recursive description to a non-recursive version using stacks.

Factorial Calculation

Recall that the factorial for an integer N can be defined recursively as follows:

Factorial(N)

Steps:

1. If (N = 0) then

2. fact = 1

3. Else

4. fact = N * Factorial(N – 1)

5. EndIf

6. Return (fact)

7. Stop

To implement the above, we require two stacks: one for storing the parameter N and another to hold the return address. No stack is necessary to store local variables, as the procedure does not possess any local variable. Let these two stacks be PARAM (for parameter) and ADDR (for return address).

We assume PUSH(X, Y) operation to push the items X and Y into the stack PARAM and ADDR, respectively.

Algorithm FactorialWithStack

Input: An integer N, and MAIN, the address of the main routine, say.

Output: Factorial value of N (that is N!).

Data structure: Array representation of stack.

Steps:

1. val = N, top = 0, addr = Step 15

2. PUSH (val, addr) // Initialize the stack

3. val = val – 1, addr = Step 11 // Next value and return address

4. If (val = 0 ) then

5. fact = 1

6. Go to Step 12

7. Else

8. PUSH(val, addr) // Val pushed into PARAM and addr pushed into ADDR

9. Go to Step 3

10. EndIf

11. fact = val * fact

12. val = POP_PARAM( ), addr = POP_ADDR( )

13. Go to addr

14. Return (fact)

15. Stop

Note that Steps 3–10 control PUSH and Steps 11–13 are POP operations. Here, the stacks are initialized by the calling value and address of the Return statement, that is, Step 14. POP_PARAM( ) and POP_ADDR( ) are the two POP operations assumed on two stacks PARAM and ADDR, respectively.

The above implementation is illustrated for N = 5 in Figure 4.6.

Figure 4.6 Computation of a factorial (recursively) using a stack.

Class Stack in Collection Framework

In Java collection framework, the class Vector is a legacy class (see Fig. 6.4). Stack is a subclass of the class Vector that implements a standard last-in, first-out data structure called stack. This means the methods which are available for the Vector class is also available to the Stack class, in addition, it has its own methods.

Figure 6.4: The class hierarchy of class Stack.

Constructor

The class Stack has the single default constructor to create an empty stack.

Methods

The methods of the class Stack are shown in Table 6.1.

Method	Description
boolean empty( )	Returns true if the stack is empty, and returns false if the stack contains elements.
E peek( )	Returns the element on the top of the stack, but does not remove it.
E pop( )	Returns the element on the top of the stack, removing it in the process.
E push(E element)	Pushes element onto the stack. element is also returned.
int search(Object element)	Searches for element in the stack. If found, its offset from the top of the stack is returned. Otherwise, –1 is returned.

Table 6.1: The methods defend in Stack class

Creating a stack object and its simple opeartions

Example 6.1 : Simple stack example with basic operations

import java.util.Stack;

public class StackBasicExample {

public static void main(String a[]){

// Creating a stack of integers

Stack<Integer> stack = new Stack<>();

System.out.println("Empty stack : " + stack);

System.out.println("Empty stack : " + stack.isEmpty());

// Following statement will throw an exception

// if we waint to pop an item from an empty stack

System.out.println("Empty stack : Pop Operation : " + stack.pop());

// Inserting some data into the stack created

stack.push(1);

stack.push(22);

stack.push(333);

stack.push(4444);

// Print the entire stack now

System.out.println("Non-Empty stack : " + stack);

System.out.println("Pop operation : " + stack.pop());

System.out.println("After pop Operation : " + stack);

System.out.println("The element at the top : " + stack.peep());

System.out.println("After peep operation : " + stack);

System.out.println("Search operation: " + stack.search(22));

System.out.println("Is stack empty? " + stack.isEmpty());

}

Initializing a stack with an array of object

Example 6.2. From an Array to Stack loading

This program illustrates how a Stack object can be created with an array of characters.

import java.util.Stack;

public class ArrayToStackExample {

public static void main(String a[]){

// The input array of expression a+b*c-5

String[] expArray = { “a”, “+”, “b” , “*”, “c”, “-“, “5”};

// Create a Stack object of type String

Stack<String> stack = new Stack<String>();

// Loading the array into stack

for(String s : expArray){

stack.push(s);

}

System.out.println("The stack : " + stack);

}

Initializing a stack with a collection object, say ArrayList of object

Example 6.3a. From an integer array to Stack loading

Let us explore on “How to create a Stack object with a given Int array” here.

import java.util.Stack;

public class ArrayToStackExample {

public static void main(String a[]){

Integer[] intArr = { 1001,1002,1003,1004};

Stack<Integer> stack = new Stack<>();

for(Integer i : intArr){

stack.push(i);

}

System.out.println("Non-Empty stack : " + stack);

}

Example 6.3b. From an ArrayList collection to Stack loading

The following program illustrates the initialization of a stack with a given List of integers stored in a collection object of type ArrayList.

import java.util.*;

public class ArrayListToStackExample {

public static void main(String a[]){

// Create a collection object of type ArrayList

ArrayList<Integer> list = new ArrayList<Integer>();

list.add(1);

list.add(2);

list.add(3);

// Declare a Stack object

Stack<Integer> stack = new Stack<Integer>();

// Loading the stack with the collection items

Stack.addAll(list); // Method is defined in the Vector class

// Printing the first item in the stack

System.out.println("Top item in the stack : " + stack.peep());

}

Copying a stack to a collection object

Example 6.4. From an ArrayList collection to Stack loading

The following program illustrates the copy of a stack to a collection object of type ArrayList.

import java.util.*;

public class StackBasicExample {

public static void main(String a[]){

// The Input stack

Stack<Integer> stack = new Stack<Integer>();

stack.push(1);

stack.push(2);

stack.push(3);

// Create a collection object of type ArrayList

ArrayList<Integer> list = new ArrayList<Integer>();

// Copy the elements in stack to the collection

list.addAll(stack);

// Printing the Stack object

System.out.println("Non-Empty stack : " + stack);

// Printing the ArrayList object

System.out.println("Non-Empty List : " + list);

}

Example 6.5. Creating a Stack and Performing basic operations like push, pop and peek

import java.util.*;

public class StackExample {

public static void main(String[] args) {

// Creating a Stack

Stack<String>stackOfCards = new Stack<>();

// Pushing new items to the Stack

stackOfCards.push("Jack");

stackOfCards.push("Queen");

stackOfCards.push("King");

stackOfCards.push("Ace");

System.out.println("Stack => " + stackOfCards);

System.out.println();

// Popping items from the Stack

String cardAtTop = stackOfCards.pop(); // Throws EmptyStackException if the stack is empty

System.out.println("Stack.pop() => " + cardAtTop);

System.out.println("Current Stack => " + stackOfCards);

System.out.println();

// Get the item at the top of the stack without removing it

cardAtTop = stackOfCards.peek();

System.out.println("Stack.peek() => " + cardAtTop);

System.out.println("Current Stack => " + stackOfCards);

}

Example 6.6. Other Stack Operations

· Check if the stack is empty.

· Find the size of the stack.

· Search for an element in the Stack.

import java.util.Stack;

public class StackSizeSearchExample {

public static void main(String[] args) {

Stack<String>stackOfCards = new Stack<>();

stackOfCards.push("Jack");

stackOfCards.push("Queen");

stackOfCards.push("King");

stackOfCards.push("Ace");

System.out.println("Stack : " + stackOfCards);

// Check if the Stack is empty

System.out.println("Is Stack empty? : " + stackOfCards.isEmpty());

// Find the size of Stack

System.out.println("Size of Stack : " + stackOfCards.size());

// Search for an element

// The search() method returns the 1-based position of the element from the top of the stack

// It returns -1 if the element was not found in the stack

int position = stackOfCards.search("Queen");

if(position != -1) {

System.out.println("Found the element \"Queen\" at position : " + position);

} else {

System.out.println("Element not found");

}

Example 6.7. The example in this section shows various ways of iterating over a Stack.

Iterate over a Stack using forEach().

Iterate over a Stack using iterator().

Iterate over a Stack using iterator() and forEachRemaining() method.

Iterate over a Stack from Top to Bottom using listIterator().

import java.util.Iterator;

import java.util.ListIterator;

import java.util.Stack;

public class IterateOverStackExample {

public static void main(String[] args) {

Stack<String>stackOfPlates = new Stack<>();

stackOfPlates.add("Plate 1");

stackOfPlates.add("Plate 2");

stackOfPlates.add("Plate 3");

stackOfPlates.add("Plate 4");

System.out.println("=== Iterate over a Stack using Java 8 forEach() method ===");

stackOfPlates.forEach(plate -> {

System.out.println(plate);

});

System.out.println("\n=== Iterate over a Stack using iterator() ===");

Iterator<String>platesIterator = stackOfPlates.iterator();

while (platesIterator.hasNext()) {

String plate = platesIterator.next();

System.out.println(plate);

}

System.out.println("\n=== Iterate over a Stack using iterator() and Java 8 forEachRemaining() method ===");

platesIterator = stackOfPlates.iterator();

while (platesIterator.hasNext()) {

String plate = platesIterator.next();

System.out.println(plate);

}

System.out.println("\n=== Iterate over a Stack from TOP to BOTTOM using listIterator() ===");

// ListIterator allows you to traverse in both forward and backward directions.

// We'll start from the top of the stack and traverse backwards.

ListIterator<String>platesListIterator = stackOfPlates.listIterator(stackOfPlates.size());

while (platesListIterator.hasPrevious()) {

String plate = platesListIterator.previous();

System.out.println(plate);

}